package 冗余连接;

import java.util.Scanner;

/**
 * @author: AirMan
 * @date: 2025/6/6 11:11
 * @description:
 * 有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图）
 * 现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图
 * 先请你找出冗余边，删除后，使该图可以重新变成一棵树。
 * 输入描述
 * 第一行包含一个整数 N，表示图的节点个数和边的个数。
 * 后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。
 * 输出描述
 * 输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。
 * 输入示例
 */
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        union_find_set unionSet = new union_find_set(n + 1);

        for (int i = 0; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            if (!unionSet.union(u, v)) {
                // 如果两条边连接失败，说明两条边在连接的话，就会出现环。那么将就可以删除这一条边！
                System.out.println(u + " " + v);
                return;
            }
        }

    }
}

class union_find_set {
    public static int[] father;
    public static int[] rank;

    public union_find_set(int n) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        rank = new int[n];
    }

    public int find(int u) {
        // 路径压缩
        if (u != father[u]) {
            u = find(father[u]);
        }
        return father[u];
    }

    public boolean union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return false;
        // 根据秩进行连接
        if (rank[u] < rank[v]) {
            father[u] = v;
        } else if (rank[u] > rank[v]) {
            father[v] = u;
        } else {
            father[v] = u;
            rank[u] += 1;
        }
        return true;
    }
}

